package com.cdream.basic.algorithm.leetcode.dp;

public class Question5 {
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int index = 0;
        int maxLength = 1;
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i + L - 1 < len; i++) {
                int endIndex = i + L - 1;
                if (s.charAt(i)!=s.charAt(endIndex)){
                    dp[i][endIndex] = false;
                }else {
                    if (L < 3) {
                        dp[i][endIndex] = true;
                    } else {
                        dp[i][endIndex] = dp[i + 1][i + L - 2];
                    }
                }


                if (dp[i][endIndex] && endIndex - i + 1 > maxLength) {
                    index = i;
                    maxLength = L;
                }
            }
        }
        return s.substring(index, index + maxLength );
    }

    public static void main(String[] args) {
        new Question5().longestPalindrome2("bb");
    }
    public String longestPalindrome2(String s) {
        // 动态规划最长回文串 P（i,j）是最长回文串
        int l = s.length();
        boolean[][] dp = new boolean[l][l];
        for(int i = 0; i<s.length();i++ ){
            dp[i][i] = true;
        }
        int begin = 0;
        int max = 1;
        char[] chars = s.toCharArray();
        for(int L = 2; L<=s.length(); L++){
            for(int left = 0; left<s.length();left++){
                int right = left + L - 1;
                if(right>= s.length()){
                    break;
                }
                if(chars[left]!=chars[right]){
                    dp[left][right] = false;
                }else {
                    if(L==2){
                        dp[left][right] = true;
                    }else {
                        dp[left][right] = dp[left+1][right-1];
                    }
                }
                if(dp[left][right] && (right-left+1)> max){
                    begin = left;
                    max = right -left +1;
                }
            }
        }
        return s.substring(begin,begin+ max);
    }
}
